{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "求解问题：\n",
    "一个农民承包了6块耕地共300亩，准备播种小麦，玉米，水果和蔬菜四种农产品，已知各种农产品的计划播种面积、每块土地种植不同农产品的单产收益\n",
    "如何进行合理安排，使得总收益最大  \n",
    "\n",
    "![avatar]()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "0. 导包，定义数据结构"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-22T03:17:22.450936Z",
     "start_time": "2020-11-22T03:17:21.709893Z"
    }
   },
   "outputs": [],
   "source": [
    "#导入包\n",
    "import numpy as np\n",
    "from pulp import *\n",
    "\n",
    "# 设置收益：4种农作物，6种不同类型的地块\n",
    "incomes = np.array([[500, 550, 630, 1000, 800, 700],\n",
    "                  [800, 700, 600, 950, 900, 930],\n",
    "                  [1000, 960, 840, 650, 600, 700],\n",
    "                  [1200, 1040, 980, 860, 880, 780]])\n",
    "# 计划播种面积\n",
    "max_plant = [76, 88, 96, 40]\n",
    "\n",
    "# 地块面积\n",
    "max_cultivation = [42, 56, 44, 39, 60, 59]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.定义线性规划的问题，求最小极值  \n",
    "Prob = LpProblem ( \"problem_name\" , sense )  \n",
    "定义Prob变量，用来定义一个LP问题实例，其中problem_name指定问题名（输出信息用），sense值是LpMinimize或LpMaximize中的一个，用来指定目标函数是求最大值还是最小值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-22T03:17:24.757067Z",
     "start_time": "2020-11-22T03:17:24.750067Z"
    }
   },
   "outputs": [],
   "source": [
    "#求最大收益\n",
    "prob = LpProblem('Transportation', sense=LpMaximize)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 定义决策变量  \n",
    "有两种方式， \n",
    " - 一种是定义单个变量(适用于变量个数不多的情况）  \n",
    "DV = LpVariable ( decision variable name , lowbound , upbound ,category )  \n",
    "decision variable name指定变量名，lowBound和upBound是下界和上界， 默认是none, 分别代表负无穷和正无穷, category用来指定变量是离散  (LpInteger,LpBinary)还是连续(LpContinuous),\n",
    "\n",
    " - 还有一种方式是用dict方式来定义大量的变量，如下：  \n",
    "Ingredients = ['Chicken','Beef','Mutton','Rice','Wheat','Gel']  \n",
    "variables = LpVariable.dicts (\"Ingr\",Ingredients,0)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-22T03:39:03.786368Z",
     "start_time": "2020-11-22T03:39:03.772367Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "row:4 col:6\n",
      "var= [[x00, x01, x02, x03, x04, x05], [x10, x11, x12, x13, x14, x15], [x20, x21, x22, x23, x24, x25], [x30, x31, x32, x33, x34, x35]]\n"
     ]
    }
   ],
   "source": [
    "#row:农作物种类\n",
    "row = len(incomes)\n",
    "\n",
    "#col:地块的种类\n",
    "col = len(incomes[0])\n",
    "print(f'row:{row} col:{col}')\n",
    "\n",
    "# 定义相关变量，x01:在地块1上种植小麦的亩数，x02:在地块1上种植小麦的亩数\n",
    "var = [[LpVariable(f'x{i}{j}', lowBound=0, cat=LpInteger) for j in range(col)] for i in range(row)]\n",
    "\n",
    "print('var=', var)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-21T14:59:38.750458Z",
     "start_time": "2020-11-21T14:59:38.740457Z"
    }
   },
   "source": [
    "3. 添加目标函数和约束条件  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-22T03:44:35.262327Z",
     "start_time": "2020-11-22T03:44:35.246326Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[x00,\n",
       " x01,\n",
       " x02,\n",
       " x03,\n",
       " x04,\n",
       " x05,\n",
       " x10,\n",
       " x11,\n",
       " x12,\n",
       " x13,\n",
       " x14,\n",
       " x15,\n",
       " x20,\n",
       " x21,\n",
       " x22,\n",
       " x23,\n",
       " x24,\n",
       " x25,\n",
       " x30,\n",
       " x31,\n",
       " x32,\n",
       " x33,\n",
       " x34,\n",
       " x35]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 递归展开列表,将上面的2维list转换成1维\n",
    "flatten = lambda x: [y for l in x for y in flatten(l)] if type(x) is list else [x]\n",
    "flatten(var)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-22T03:57:02.326057Z",
     "start_time": "2020-11-22T03:57:02.307056Z"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\ProgramData\\Anaconda3\\lib\\site-packages\\pulp\\pulp.py:1530: UserWarning: Overwriting previously set objective.\n",
      "  warnings.warn(\"Overwriting previously set objective.\")\n"
     ]
    }
   ],
   "source": [
    "#添加目标方程，求解的是种地的收益，sum(每个地块上种植农作物的亩数*收益)\n",
    "prob += pulp.lpDot(flatten(var), incomes.flatten())\n",
    "\n",
    "#添加约束条件\n",
    "for i in range(row):\n",
    "    #每种农作物的计划播种面积进行约束\n",
    "    prob += pulp.lpSum(var[i]) <= max_plant[i]\n",
    "    \n",
    "for j in range(col):\n",
    "    #每个地块可种植的面积进行约束\n",
    "    prob += pulp.lpSum([var[i][j] for i in range(row)]) <= max_cultivation[j]\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. 求解\n",
    "\n",
    "Prob.slove ( )  \n",
    "输出的结果是’Optimal’，说明找到了最优解。my_lp_problem.status是一个常量，pulp.LpStatus是一个dict，把常量变成可读的字符串：\n",
    "\n",
    "LpStatus = {  \n",
    "    LpStatusNotSolved:\"Not Solved\",  \n",
    "    LpStatusOptimal:\"Optimal\",  \n",
    "    LpStatusInfeasible:\"Infeasible\",  \n",
    "    LpStatusUnbounded:\"Unbounded\",  \n",
    "    LpStatusUndefined:\"Undefined\",  \n",
    "    }    \n",
    "    \n",
    "这些常量的含义是：\n",
    "\n",
    "Not Solved：还没有调研solve()函数前的状态。  \n",
    "Optimal：找到了最优解。  \n",
    "Infeasible：问题没有可行解(比如定义了constraints x <= 1并且x >=2这样的约束)。  \n",
    "Unbounded：约束条件是无界的(not bounded)，最大化会导致无穷大(比如只有一个x >= 3这样的约束)。  \n",
    "Undefined：最优解可能存在但是没有求解出来。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-22T03:57:23.841287Z",
     "start_time": "2020-11-22T03:57:23.678278Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Status: Optimal\n"
     ]
    }
   ],
   "source": [
    "#求解\n",
    "prob.solve()\n",
    "# 查看解的状态, “Not Solved”, “Infeasible”, “Unbounded”, “Undefined” or “Optimal”\n",
    "print(\"Status:\", LpStatus[prob.status])\n",
    "#print('prob.status:', prob.status)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-21T15:06:27.489031Z",
     "start_time": "2020-11-21T15:06:27.480030Z"
    }
   },
   "source": [
    "5. 查看结果\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-11-22T03:59:24.608195Z",
     "start_time": "2020-11-22T03:59:24.593194Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最大收益为284230.0\n",
      "各变量的取值为：\n",
      "[[0.0, 0.0, 6.0, 39.0, 31.0, 0.0],\n",
      " [0.0, 0.0, 0.0, 0.0, 29.0, 59.0],\n",
      " [2.0, 56.0, 38.0, 0.0, 0.0, 0.0],\n",
      " [40.0, 0.0, 0.0, 0.0, 0.0, 0.0]]\n"
     ]
    }
   ],
   "source": [
    "from pprint import pprint\n",
    "# 查看解\n",
    "result = {'objective':value(prob.objective), \\\n",
    "              'var': [[value(var[i][j]) for j in range(col)] for i in range(row)]}\n",
    "\n",
    "# 输出结果\n",
    "print(f'最大收益为{result[\"objective\"]}')\n",
    "print('各变量的取值为：')\n",
    "pprint(result['var'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. 总结  \n",
    "思考程序本质：\n",
    "  problem对象是如何通过不断加来获得目标函数和约束的？熟悉python或者c++的朋友可能会想到一个词：操作符重载。  \n",
    "  没错，就是这么实现的，上述的对象几乎都实现了不同的重载。  \n",
    "  首先是Problem对象prob，全名pulp.pulp.LpProblem；当打印输出（print）时，会打印出问题名，当不断增加目标函数、约束时，也会随着print输出；而它的__add__一定是被定义过了，我们先说其他对象。 \n",
    "  当我们定义一个变量时，它的类型是pulp.pulp.LpVariable，当我们对这些变量和其他变量做加法、和其他常数做乘法时，它会返回一个新的对象，  经检测，这个新对象的类名叫pulp.pulp.LpAffineExpression，顾名思义，叫做关系表达式；如果print，会打印这个关系表达式。  \n",
    "  而如果对关系表达式做出：>=、<=、==时，会返回新的对象，类名叫做pulp.pulp.LpConstraint，即约束对象；如果print，会打印这个约束。  \n",
    "  将关系表达式（pulp.pulp.LpAffineExpression）与问题（pulp.pulp.LpProblem）相加时，会返回新的问题对象，并且新的问题对象会将这个关系表达式作为目标函数。  \n",
    "  将约束对象（pulp.pulp.LpConstraint）与问题（pulp.pulp.LpProblem）相加时，会返回新的问题对象，并且这个新的问题对象会多出约束对象所代表的约束条件。  \n",
    "  调用问题对象的solve方法，解出线性规划的解。  \n",
    "  访问问题对象的objective成员变量，会得到目标函数（关系表达式对象）。  \n",
    "  调用pulp的value方法，将获得对变量代入值的结果，如果是关系表达式对象，将获得优化结果；如果是变量对象，将获得优化结果达到时的变量取值；如果是None，说明你忘调用solve了。  "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
